package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何对链表进行重新排序

// 给定链表 L0 -> L1 -> L2 ... Ln-1 -> Ln
// 将链表重新排序为 L0 -> Ln -> L1 -> Ln-1 ...
// 在原来链表的基础上进行排序，即不能申请新的节点
// 只能修改节点的 next 域，不能修改数据域

// 首先找到链表的中间节点
// 对链表的后半部分子链表进行逆序
// 把链表的前半部分与逆序后的后半部分进行合并

func main() {
	head := &common.LNode{}
	common.CreateNode1(head, 8)
	fmt.Println("排序前：", head)
	Reorder(head)
	fmt.Println("排序后：", head)
}

func Reorder(head *common.LNode) {
	if head == nil || head.Next == nil {
		return
	}

	current1 := head.Next
	middle := findMiddleNode(head.Next)
	current2 := reverse(middle)

	var temp *common.LNode
	for current1.Next != nil {
		temp = current1.Next
		current1.Next = current2
		current1 = temp
		temp = current2.Next
		current2.Next = current1
		current2 = temp
	}

	current1.Next = current2
}

// 寻找中间节点，后半段不小于前半段长度
func findMiddleNode(head *common.LNode) *common.LNode {
	if head == nil || head.Next == nil {
		return head
	}

	fast := head // 遍历链表时每次向前走两步
	slow := head // 遍历链表时每次向前走一步
	slowPrevious := head

	for fast != nil && fast.Next != nil {
		slowPrevious = slow
		slow = slow.Next
		fast = fast.Next.Next
	}

	slowPrevious.Next = nil
	return slow
}

func reverse(head *common.LNode) *common.LNode {
	if head == nil || head.Next == nil {
		return head
	}

	current := head
	var previous, next *common.LNode

	for current != nil {
		next = current.Next
		current.Next = previous
		previous = current
		current = next
	}

	return previous
}
